perm filename DES[NBS,WD] blob
sn#421006 filedate 1978-11-10 generic text, type T, neo UTF8
\!ODDSEC(DES,APPENDIX C - THE DATA ENCRYPTION STANDARD);
\!EPSILONLAMBDASET(30,0);
\!RUNTIT(Introduction);
\!PARA;The algorithm is designed to encipher and decipher blocks of data
consisting of 64 bits under control of a 64 bit key. Deciphering must be
accomplished by using the same key as for enciphering, but with the
schedule of addressing the key bits altered so that the deciphering process
is the reverse of the enciphering process. A block to be enciphered is
subjected to an initial permutation IP, then to a complex key-dependent
computation and finally to a permutation which is the inverse of the
initial permutation IP\∩-1\⊗. The key-dependent computation can be simply
defined in terms of a function f, called the cipher function, and a
function KS, called the key schedule. A description of the computation is
given first, along with details as to how the algorithm is used for
encipherment. Next, the use of the algorithm for decipherment is
described. Finally, a definition of the cipher function f is given in
terms of primitive functions which are called the selection functions S\∪i\⊗
and the permutation function. S\∪i\⊗, P and KS of the algorithm are contained
in the Appendix.\!EP;
\!PARA; The following notation is convenient: Given two blocks L and R of
bits, LR denotes the block consisting of the bits of L followed by the bits
of R. Since concatenation is associative B\∪1\⊗B\∪2\⊗...B\∪8\⊗, for example, denotes
the block consisting of the bits of B\∪1\⊗ followed by the bits of B\∪2\⊗...
followed by the bits of B\∪8\⊗.\!EP;
\!RUNTIT(Enciphering);
\!PARA; A sketch of the enciphering computation is given in Figure 1.\!EP;
\!PARA; The 64 bits of the input block to be enciphered are first subjected
to the following permutation, called the initial permutation IP:\!EP;
IP
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
\!PARA; That is the permuted input has bit 58 of the input as its first
bit, bit 50 as its second bit, and so on with bit 7 as its last bit. The
permuted input block is then the input to a complex key-dependent
computation described below. The output of that computation, called the
preoutput, is then subjected to the following permutation which is the
inverse of the initial permutation:\!EP;
\!EPSILONLAMBDASET(25,0);
ENCIPHERING COMPUTATION
---------------------------------------------
| INPUT |
---------------------------------------------
↓
--------------------------
( INITIAL PERMUTATION )
--------------------------
|
-----------------o-----------------
↓ ↓
PERMUTED --------------------------- ---------------------------
INPUT | L\∪0\⊗ | | R\∪0\⊗ |
--------------------------- ---------------------------
| _________________|_________________K\∪1\⊗
↓ ↓ |
(+)←-------------(f)---------------o
|________________ ________________|
_________________X_________________
↓ ↓
--------------------------- ---------------------------
| L\∪1\⊗ = R\∪0\⊗ | | R\∪1\⊗ = L\∪0\⊗(+)f(R\∪0\⊗,K\∪1\⊗) |
--------------------------- ---------------------------
| _________________|_________________K\∪2\⊗
↓ ↓ |
(+)←-------------(f)---------------o
|________________ ________________|
_________________X_________________
↓ ↓
--------------------------- ---------------------------
| L\∪2\⊗ = R\∪1\⊗ | | R\∪2\⊗ = L\∪1\⊗(+)f(R\∪1\⊗,K\∪2\⊗) |
--------------------------- ---------------------------
| _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _K\∪n\⊗
↓ ↓ |
(+)←- - - - - - -(f)← - - - - - - -o
|_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _|
_ _ _ _ _ _ _ _ X _ _ _ _ _ _ _ _
↓ ↓
--------------------------- ---------------------------
| L\∪15\⊗ = R\∪14\⊗ | | R\∪15\⊗ = L\∪14\⊗(+)f(R\∪14\⊗,K\∪15\⊗) |
--------------------------- ---------------------------
| _________________|_________________K\∪16\⊗
↓ ↓ |
(+)←-------------(f)---------------o
↓ ↓
--------------------------- ---------------------------
PREOUTPUT | R\∪16\⊗ = L\∪15\⊗(+)f(R\∪15\⊗,K\∪16\⊗) | | L\∪16\⊗ = R\∪15\⊗ |
--------------------------- ---------------------------
| |
-----------------o-----------------
↓
--------------------------
( INVERSE INITIAL PERM )
--------------------------
↓
---------------------------------------------
| OUTPUT |
---------------------------------------------
Figure 1
\!EPSILONLAMBDASET(30,0);
IP\∩-1\⊗
40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25
\!PARA; That is, the output of the algorithm has bit 40 of the preoutput
block as its first bit, bit 8 as its second bit, and so on, until bit 25 of
the preoutput block is the last bit of the output.\!EP;
\!PARA; The computation which uses the permuted input block as its input to
produce the preoutput block consists, but for a final interchange of
blocks, of 16 iterations of a calculation that is described below in terms
of the cipher function f which operates on two blocks, one of 32 bits and
one of 48 bits, and produces a block of 32 bits.\!EP;
\!PARA; Let the 64 bits of the input block to an iteration consist of a 32
bit block L followed by a 32 bit block R. Using the notation defined in
the introduction, the input block is then LR.\!EP;
\!PARA; Let K be a block of 48 bits chosen from the 64 bit key. Then the
output L'R' of an iteration with input LR is defined by:\!EP;
(1) L' = R
R' = L \fA4 f(R,K)
where \fA4 denotes bit-by-bit addition modulo 2.
\!PARA; As remarked before, the input of the first iteration of the
calculation is the permuted input block. If L'R' is the output of the 16th
iteration then R'L' is the preoutput block. At each iteration a different
block K of key bits is chosen from the 64 bit key designated by KEY.\!EP;
\!PARA; With more notation we can describe the iterations of the
computation in more detail. Let KS be a function which takes an integer n
in the range from 1 to 16 and a 64 bit block KEY as input and yields as
output a 48 bit block Kn which is a permuted selection of bits from KEY.
That is\!EP;
(2) K\∪n\⊗ = KS(n,KEY)
with Kn determined by the bits in 48 distinct bit positions of KEY. KS is
called the key schedule because the block K used in the n'th iteration of
(1) is the block K\∪n\⊗ determined by (2).
\!PARA; As before, let the permuted input block be LR. Finally, let L\∪0\⊗ and
R\∪0\⊗ be respectively L and R and let L\∪n\⊗ and Rn be respectively L' and R' of
(1) when L and R are respectively L\∪n-1\⊗ and R\∪n-1\⊗ and K is K\∪n\⊗; that is, when
n is in the range from 1 to 16,\!EP;
(3) L\∪n\⊗ = R\∪n-1\⊗
R\∪n\⊗ = L\∪n-1\⊗ \fA4 f(R\∪n-1\⊗,K\∪n\⊗)
The preoutput block is then R\∪16\⊗L\∪16\⊗.
\!PARA; The key schedule KS of the algorithm is described in detail in the
Appendix. The key schedule produces the 16 Kn which are required for the
algorithm.\!EP;
\!RUNTIT(Deciphering);
\!PARA; The permutation IP\∩-1\⊗ applied to the preoutput block is the inverse
of the initial permutation IP applied to the input. Further, from (1) it
follows that:\!EP;
(4) R = L'
L = R' \fA4 f(L',K)
\!PARA; Consequently, to decipher it is only necessary to apply the very
same algorithm to an enciphered message block, taking care that at each
iteration of the computation the same block of key bits K is used during
decipherment as was used during the encipherment of the block. Using the
notation of the previous section, this can be expressed by the
equations:\!EP;
(5) R\∪n-1\⊗ = L\∪n\⊗
L\∪n-1\⊗ = R\∪n\⊗ \fA4 f(L\∪n\⊗,K\∪n\⊗)
where now L\∪16\⊗R\∪16\⊗ is the premuted input block for the deciphering
calculation and L\∪1\⊗R\∪1\⊗ is the preoutput block. That is, for the decipherment
calculation with R\∪16\⊗L\∪16\⊗ as the permuted input, K\∪16\⊗ is used in the first
iteration, K\∪15\⊗ in the second, and so on, with K\∪1\⊗ used in the 16th
iteration.
\!RUNTIT(The Cipher Function f);
\!PARA; A sketch of the calculation of f(R,K) is given in Figure 2.\!EP;
\!EPSILONLAMBDASET(25,-5);
CALCULATION OF f(R,K)
-------------------------
| R (32 bits) |
-------------------------
|
↓
-
( E )
-
|
↓
--------------------------------- ---------------------------------
| 48 bits | | K (48 bits) |
--------------------------------- ---------------------------------
| |
| |
| - |
--------------------→( + )←-------------------
-
|
↓
----------------------------------------------------------------------------
|||||| |||||| |||||| |||||| |||||| |||||| |||||| ||||||
------ ------ ------ ------ ------ ------ ------ ------
( S\∪1\⊗ ) ( S\∪2\⊗ ) ( S\∪3\⊗ ) ( S\∪4\⊗ ) ( S\∪5\⊗ ) ( S\∪6\⊗ ) ( S\∪7\⊗ ) ( S\∪8\⊗ )
------ ------ ------ ------ ------ ------ ------ ------
|||| |||| |||| |||| |||| |||| |||| ||||
|||| |||| |||| |||| |||| |||| |||| ||||
--------------------------------------------------------------------------
|
↓
-
( P )
-
|
↓
-------------------------
| 32 bits |
-------------------------
Figure 2
\!EPSILONLAMBDASET(30,0);
\!PARA; Let E denote a function which takes a block of 32 bits as input and
yields a block of 48 bits as output. Let E be such that the 48 bits of its
output, written as 8 blocks of 6 bits each, are obtained by selecting the
bits in its inputs in order according to the following table:\!EP;
E BIT-SELECTION TABLE
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
\!PARA; Thus the first three bits of E(R) are the bits in positions 32, 1
and 2 of R while the last 2 bits of E(R) are the bits in positions 32 and 1.\!EP;
\!PARA; Each of the unique selection functions S\∪1\⊗, S\∪2\⊗, ..., S\∪8\⊗, takes a 6
bit block as input and yields a 4 bit block as output and is illustrated by
using a table containing the recommended S\∪1\⊗:\!EP;
S\∪1\⊗
Column Number
Row |
No. | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
|________________________________________________________________
|
0 | 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 | 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 | 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 | 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
If S\∪1\⊗ is the function defined in this table and B is a block of 6 bits,
then S\∪1\⊗(B) is determined as follows: The first and last bits of B
represent in base 2 a number in the range 0 to 3. Let that number be i.
The middle 4 bits of B represent in base 2 a number in the range 0 to 15.
Let that number be j. Look up in the table the number in the i'th row and
j'th column. It is a number in the range 0 to 15. and is uniquely
represented by a 4 bit block. That block is the output S\∪1\⊗(B) of S\∪1\⊗ for the
input B. For example, the input 011011 the row is 01, that is row 1, and
the column is determined by 1101, that is column 13. In row 1 column 13
appears 5 so that the output is 0101. Selection functions S\∪1\⊗,S\∪2\⊗,...,S\∪8\⊗ of
the algorithm appear in the Appendix.
\!PARA; The permutation function P yields a 32 bit output from a 32 bit
input by permuting the bits of the input block. Such a function is defined
by the following table:\!EP;
P
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
\!PARA; The output P(L) for the function P defined by this table is
obtained from the input L by taking the 16th bit of L as the first bit of
P(L), the 7th bit as the second bit of P(L), and so on until the 25th bit
of L is taken as the 32nd bit of P(L). The permutation function P of the
algorithm is repeated in the Appendix.\!EP;
\!PARA; Now let S\∪1\⊗,...,S\∪8\⊗ be eight distinct selection functions, let P be
the permutation function and let E be the function defined above.\!EP;
\!PARA; To define f(R,K) we first define B\∪1\⊗,...,B\∪8\⊗ to be blocks of 6 bits
each for which
(6) B\∪1\⊗B\∪2\⊗...B\∪8\⊗ = K \fA4 E(R)
\!PARA; The block f(R,K) is then defined to be\!EP;
(7) P(S\∪1\⊗(B\∪1\⊗)S\∪2\⊗(B\∪2\⊗)...S\∪8\⊗(B\∪8\⊗))
\!PARA; Thus K \fA4 E(R) is first divided into the 8 blocks as indicated
in (6). Then each Bi is taken as an input to S\∪i\⊗ and the 8 blocks
S\∪1\⊗(B\∪1\⊗),S\∪2\⊗(B\∪2\⊗),...S\∪8\⊗(B\∪8\⊗) of 4 bits each are consolidated into a single block
of 32 bits which forms the input to P. The output (7) is then the output of
the function f for the inputs R and K.\!EP;
PRIMITIVE FUNCTIONS FOR THE
DATA ENCRYPTION ALGORITHM
\!PARA; The choice of the primitive functions KS, S\∪1\⊗, ..., S\∪8\⊗ and P is
critical to the strength of an encipherment resulting from the algorithm.
Specified below is the recommended set of functions, describing S\∪1\⊗, ..., S\∪8\⊗
and P in the same way they are described in the algorithm. For the
interpretation of the tables describing these functions, see the discussion
in the body of the algorithm.\!EP;
The primitive functions S\∪1\⊗,...,S\∪8\⊗, are:
S\∪1\⊗
14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
S\∪2\⊗
15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
S\∪3\⊗
10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12
S\∪4\⊗
7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
S\∪5\⊗
2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3
S\∪6\⊗
12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
S\∪7\⊗
4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
S\∪8\⊗
13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11
The primitive function P is:
P
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
\!PARA; Recall that K\∪n\⊗, for 1≤n≤16, is the block of 48 bits in (2) of the
algorithm. Hence, to describe KS, it is sufficient to describe the
calculation of K\∪n\⊗ from KEY for n=1, 2, ..., 16. That calculation is
illustrated in Figure 3. To complete the definition of KS it is therefore
sufficient to describe the two permuted choices, as well as the schedule of
left shifts. One bit in each eight-bit byte of the KEY may be utilized for
error detection in key generation, distribution and storage. Bits 8, 16,
..., 64 are for use in assuring that each byte is of odd parity.\!EP;
\!PARA; Permuted choice 1 is determined by the following table:\!EP;
PC-1
57 49 41 33 25 17 9
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 3 60 52 44 36
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
\!EPSILONLAMBDASET(25,-5);
KEY SCHEDULE CALCULATION
---------------------------------------------
| KEY |
---------------------------------------------
|
↓
---------------
( PERMUTED )
( CHOICE 1 )
---------------
|
↓
---------------------------
↓ ↓
-------------------- --------------------
| C\∪0\⊗ | | D\∪0\⊗ |
-------------------- --------------------
↓ ↓
----------- -----------
( LEFT ) ( LEFT )
( SHIFT ) ( SHIFT )
----------- -----------
↓ ↓
-------------------- --------------------
| C\∪1\⊗ | | D\∪1\⊗ |
-------------------- --------------------
| ↓ ------------
|-------------------------------------→( PERMUTED )--→ K\∪1\⊗
↓ ↓ ( CHOICE 2 )
----------- ----------- ------------
( LEFT ) ( LEFT )
( SHIFTS ) ( SHIFTS )
----------- -----------
↓ ↓
-------------------- --------------------
| C\∪n\⊗ | | D\∪n\⊗ |
-------------------- --------------------
| ↓ ------------
|-------------------------------------→( PERMUTED )--→ K\∪n\⊗
↓ ↓ ( CHOICE 2 )
----------- ----------- ------------
( LEFT ) ( LEFT )
( SHIFTS ) ( SHIFTS )
----------- -----------
↓ ↓
-------------------- --------------------
| C\∪16\⊗ | | D\∪16\⊗ |
-------------------- --------------------
| ↓ ------------
|-------------------------------------→( PERMUTED )--→ K\∪16\⊗
( CHOICE 2 )
------------
Figure 3
\!EPSILONLAMBDASET(30,0);
\!PARA; The table has been divided into two parts, with the first part
determining how the bits of C\∪0\⊗ are chosen, and the second part determining
how the bits of D\∪0\⊗ are chosen. The bits of KEY are numbered 1 through 64.
The bits of C\∪0\⊗ are respectively bits 57, 49, 41, ..., 44 and 36 of KEY,
with the bits of D\∪0\⊗ being bits 63, 55, 47, ..., 12 and 4 of KEY.\!EP;
\!PARA; With C\∪0\⊗ and D\∪0\⊗ defined, we how define how the blocks C\∪n\⊗ and D\∪n\⊗ are
obtained from the blocks C\∪n-1\⊗ and D\∪n-1\⊗, respectively, for n = 1, 2, ...,
16. That is accomplished by adhering to the following schedule of left
shifts of the individual blocks:\!EP;
Iteration Number of
Number Left Shifts
1 1
2 1
3 2
4 2
5 2
6 2
7 2
8 2
9 1
10 2
11 2
12 2
13 2
14 2
15 2
16 1
\!PARA; For example, C\∪3\⊗ and D\∪3\⊗ are obtained from C\∪2\⊗ and D\∪2\⊗, respectively,
by two left shifts, and C\∪16\⊗ and D\∪16\⊗ are obtained from C\∪15\⊗ and D\∪15\⊗,
respectively, by one left shift. In all cases, by a single left shift is
meant a rotation of the bits one place to the left, so that after one left
shift the bits in the 28 positions are the bits that were previously in
positions 2, 3, ..., 28, 1.\!EP;
\!PARA; Permuted choice 2 is determined by the following table:\!EP;
PC-2
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
\!PARA; Therefore, the first bit of Kn is the 14th bit of CnDn, the second
bit the 17th, and so on with the 47th bit the 29th, and the 48th bit the
32nd.\!EP;